Group Shifted Strings

Given a string, we can “shift” each of its letter to its successive letter, for example: “abc” -> “bcd”. We can keep “shifting” which forms the sequence:

  1. "abc" -> "bcd" -> ... -> "xyz"

Given a list of strings which contains only lowercase alphabets, group all strings that belong to the same shifting sequence.

For example, given: ["abc", "bcd", "acef", "xyz", "az", "ba", "a", "z"],

A solution is:

  1. [
  2.   ["abc","bcd","xyz"],
  3.   ["az","ba"],
  4.   ["acef"],
  5.   ["a","z"]
  6. ]

Solution:

  1. public class Solution {
  2.   public List<List<String>> groupStrings(String[] strings) {
  3.     List<List<String>> res = new ArrayList<>();
  4.     Map<String, List<String>> map = new HashMap<>();
  6.     for (int i = 0; i < strings.length; i++) {
  7.       String s = strings[i];
  8.       String key = hash(s);
  10.       List<String> list = map.containsKey(key) ? map.get(key) : new ArrayList<String>();
  11.       list.add(s);
  12.       map.put(key, list);
  13.     }
  15.     for (List<String> list : map.values()) {
  16.       Collections.sort(list);
  17.       res.add(list);
  18.     }
  20.     return res;
  21.   }
  23.   String hash(String s) {
  24.     String key = "";
  26.     for (int i = 1; i < s.length(); i++) {
  27.       int diff = (int)(s.charAt(i) - s.charAt(i - 1));
  28.       if (diff < 0) diff += 26;
  29.       key += String.valueOf(diff);
  30.     }
  32.     return key;
  33.   }
  34. }